package 力扣.二分;

public class 搜索插入位置35 {
    public int searchInsert(int[] nums, int target) {
         if(nums == null || nums.length == 0){
             return -1;
         }
         int N = nums.length;
//         int ans = lowerBound(nums,N,target);
//        return ans;//不管找没找到，ans就是target在有序数组的位置
        int ans = upperBound(nums, N, target);
        ans--;
         return ans >= 0 && ans < N && nums[ans] == target ? ans : ++ans;//若找到，则(--ans)就是target的位置，若找不到则ans就是target在有序数组的位置
    }

    /**
     * 使用地板函数解决
     */
    private int lowerBound(int[] nums,int N ,int target){
        int l = 0,r = N;
        while (l < r){
            int m = l + ((r - l) >> 1);
            if (nums[m] < target){
                l = m + 1;
            }else{
                r = m;
            }
        }
        return l;
    }

    /**
     * 使用天花板函数解决
     */
    private int upperBound(int[] nums ,int N,int target){
        int l = 0,r = N;
        while (l < r){
            int m = l + ((r - l) >> 1);
            if (nums[m] <= target){
                l = m + 1;
            }else {
                r = m;
            }
        }
        return l;
    }
}
